﻿// 单向循环链表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include<stdio.h>
#include<stdlib.h>
// 单向循环链表
struct Node
{
    int data;   // 数据域
    Node* next; // 地址域
};

struct Link
{
    Node* head; // 指向链表的头节点指针
};

// 初始化，生成头节点，并把地址域指向头
void Init(Link* link)
{
    link->head = (Node*)malloc(sizeof(Node));
    link->head->next = link->head;


}
//销毁循环链表
void Destory(Link* link)//写函数代码判断条件最好判断当前元素，处理当前元素。这样可以有效的减少错误的产生。
{
    Node* p = link->head->next;//用指针p指向第一个节点
    while (p != link->head)//判断p是否指向头结点
    {
        Node* q = p->next;//用指针记录头结点指向的下一个节点
        free(p);//释放头结点
        p = q;//让头指针指向下一节点
    }
    free(link->head);
}
//单向循环列表的尾插法
void InsertTail(Link* link, int val)
{
    /*创建并初始化一个新节点
    * 找链表的尾节点
    * 让新节点的地址域指向头结点
    * 让尾节点的地址域指向新节点
    */
    Node* node = (Node*)malloc(sizeof(Node));
    node->next = NULL;
    node->data = val;
    Node* p = link->head;
    while (p->next != link->head)
    {
        p = p->next;
    }
    node->next = p->next;
    p->next = node;
}
//单向循环链表头插法
void InsertHead(Link* link, int val)
{
    /*定义一个新节点并初始化
    * 将新结点的地址域指向link->head->addr
    * 将头结点的地址域指向新节点
    */
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->next = link->head->next;
    link->head->next = node;
}
//约瑟夫环问题
//有number个人围成一圈，从开头数k个，然后人出列，
//从出列的地方重新开始数K，再出列，循环往复，输出出列的人的顺序
void Josephy(Link* link)
{
    Node* p1 = link->head;//
    Node* p2 = link->head->next;
    int k = 0;
    printf("K:");
    scanf("%d", &k);
    getchar();
    while (link->head != link->head->next)
    {
        int i = 1;
        while (i < k)
        {
            p1 = p2;
            p2 = p2->next;
            i++;

            if (p2 == link->head)
            {
                p1 = p2;
                p2 = p2->next;

            }



        }

        p1->next = p2->next;
        printf("%d ", p2->data);
        free(p2);
        p2 = p1->next;
        if (p2 == link->head)
        {
            p1 = p2;
            p2 = p2->next;

        }
    }
}
void ShowLink(Link* link)
{
    Node* p = link->head->next;
    while (p != link->head)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    Link link;
    Init(&link);
    InsertTail(&link, 20);
    InsertTail(&link, 32);
    InsertTail(&link, 78);
    InsertTail(&link, 21);
    InsertTail(&link, 73);
    InsertTail(&link, 64);
    InsertTail(&link, 28);
    InsertTail(&link, 59);
    ShowLink(&link);
    InsertHead(&link, 1);
    InsertHead(&link, 3);
    InsertHead(&link, 5);
    InsertHead(&link, 7);
    InsertHead(&link, 9);
    InsertHead(&link, 11);
    ShowLink(&link);
    Josephy(&link);



}
